def findMaxSubarray(array, left, right):
    if left == right:
        return (left, right, array[left])
    (sub_left, sub_right, sub_sum) = findMaxSubarray(array[0:right], left, right-1)
    end_sum = array[right]
    cur_sum = end_sum
    end_left = right
    for i in range(right-1,left-1,-1):
        cur_sum += array[i]
        if cur_sum > end_sum:
            end_sum = cur_sum
            end_left = i
    if sub_sum > end_sum:
        return (sub_left, sub_right, sub_sum)
    else:
        return (end_left, right, end_sum)
if __name__ == '__main__':
    A  = [1, -4, 3, -4]
    print(findMaxSubarray(A, 0, 3))


